#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
char buf[1<<23],*p1=buf,*p2=buf,obuf[1<<23],*O=obuf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)) x=x*10+(ch^48),ch=getchar();
    return x*f;
}
#define int long long
const int N=1e5+5;
int n,k,q,a[N];
struct name{
    int x,l,r;
}qu[N];
namespace n2{
    const int N=1e3+5,M=1e5+5;
    int le[M],ri[M],top,z[M],inf=1e18;
    int t[N][N],laz,T[N][N];
    void work(){
        z[top=1]=0;
        for(int i=1;i<=n;i++){
            while(a[i]>=a[z[top]]) top--;
            le[i]=z[top];
            z[++top]=i;
        }
        z[top=1]=n+1;
        for(int i=n;i;i--){
            while(a[i]>=a[z[top]]) top--;
            ri[i]=z[top];
            z[++top]=i;
        }
    }
    int dfs(int l,int r){
        if(r<N){
            if(T[l][r]!=laz) t[l][r]=0,T[l][r]=laz;
            if(t[l][r]) return t[l][r];
        }
        int ans=0;
        if(l==0&&r==n+1) ans=0;
        else if(a[l]<a[r]) ans=dfs(le[l],r)+1;
        else if(a[l]>a[r]) ans=dfs(l,ri[r])+1;
        else ans=dfs(le[l],ri[r])+1;
        if(r<N) return t[l][r]=ans;
        else return ans;
    }
    int main(){
        a[0]=a[n+1]=inf;
        for(int j=1;j<=q;j++){
            laz++;
            int x=qu[j].x,l=qu[j].l,r=qu[j].r,ans=0;
            swap(a[x],a[x+1]);
            work();
            for(int i=l;i<=r;i++){
                ans+=dfs(le[i],ri[i])*k+n-1;
            }
            cout<<ans<<"\n";
        }
        return 0;
    }
}
namespace sub_x2{
    int l[N][2],r[N][2],z[N],top,w[N][2],cf[N][2],sum[N][2];
    unordered_map<int,int> t;
    void work(int k){
        t.clear();
        for(int i=1;i<=n;i++){
            if(t[a[i]]) cf[t[a[i]]][k]++,cf[i+1][k]--;
            else t[a[i]]=i;
        }
        for(int i=1;i<=n;i++) sum[i][k]=sum[i-1][k]+cf[i][k];
        top=0;
        for(int i=1;i<=n;i++){
            while(top&&a[i]>=z[top]) top--;
            l[i][k]=top;
            z[++top]=a[i];
        }
        top=0;
        for(int i=n;i;i--){
            while(top&&a[i]>=z[top]) top--;
            r[i][k]=top;
            z[++top]=a[i];
        }
    }
    int main(){
        work(0);
        swap(a[qu[1].x],a[qu[1].x+1]);
        work(1);
        for(int i=1;i<=n;i++){
            for(int k=0;k<=1;k++) l[i][k]+=l[i-1][k],sum[i][k]+=sum[i-1][k];
        }
        for(int i=n;i;i--){
            for(int k=0;k<=1;k++) r[i][k]+=r[i+1][k];
        }
        for(int i=1;i<=q;i++){
            cout<<(l[qu[i].r][i&1]-l[qu[i].l-1][i&1]+r[qu[i].l][i&1]-r[qu[i].r+1][i&1]-(sum[qu[i].r][i&1]-sum[qu[i].l-1][i&1]))*k+(qu[i].r-qu[i].l+1)*(n-1)<<"\n";
        }
        return 0;
    }
}
int lr=1,v10=1,x2=1;
signed main(){
    freopen("summer.in","r",stdin);
    freopen("summer.out","w",stdout);
    n=read(),k=read();
    for(int i=1;i<=n;i++){
        a[i]=read();
        if(a[i]>10) v10=0;
    }
    q=read();
    for(int i=1;i<=q;i++){
        qu[i].x=read(),qu[i].l=read(),qu[i].r=read();
        if(qu[i].l!=qu[i].r) lr=0;
        if(qu[i].x!=qu[1].x) x2=0;
    }
    if(n<=1e3||v10) n2::main();
    else if(x2) sub_x2::main();
    else n2::main();
    return 0;
}